package classical_problems_150;

import java.util.ArrayList;
import java.util.List;

public class P_0068 {
    public List<String> fullJustify(String[] words, int maxWidth) {
        List<String> res = new ArrayList<>();
        int line_num = 0;
        int line_start_index = 0;
        int line_width = 0;
        for(int i=0; i<words.length; i++){
            line_width += words[i].length() + 1;
            if(line_width>=maxWidth || i==words.length-1){
                int extra_space_num = 0;
                int line_end_index = 0;
                // 只是多余一个空格
                if(line_width-1 <= maxWidth){
                    line_width -= 1;
                    line_end_index = i;
                    extra_space_num = maxWidth - line_width;
                } else {
                    line_end_index = i-1;
                    line_width -= words[i].length() + 1 + 1;
                    extra_space_num = maxWidth - line_width;
                    i--;
                }

                int line_word_num = line_end_index - line_start_index + 1;
                String s;
                if(line_word_num==1){
                    // 单个单词，左对齐，填充空格
                    s = words[line_end_index] + " ".repeat(maxWidth-words[line_end_index].length());
                } else if(line_end_index==words.length-1){
                    // 最后一行
                    StringBuilder builder = new StringBuilder();
                    for(int j=line_start_index; j<line_end_index; j++){
                        builder.append(words[j]).append(" ");
                    }
                    builder.append(words[line_end_index]);
                    s = builder.toString();
                    s += " ".repeat(maxWidth - s.length());
                } else{
                    StringBuilder builder = new StringBuilder();
                    int right_space_num = 1 + extra_space_num / (line_word_num - 1);
                    String spaces = " ".repeat(right_space_num);
                    int left_num = extra_space_num % (line_word_num - 1);
                    for(int j=line_start_index; j<line_end_index; j++){
                        builder.append(words[j]).append(spaces);
                        if((j-line_start_index)<left_num){
                            builder.append(" ");
                        }
                    }
                    builder.append(words[line_end_index]);
                    s = builder.toString();
                }
                res.add(s);
                line_start_index = line_end_index + 1;
                line_width = 0;

            }
        }
        return res;
    }

    public static void main(String[] args){
        P_0068 solution = new P_0068();
        String[] words = {"This", "is", "an", "example", "of", "text", "justification."};
        List<String> res = solution.fullJustify(words, 16);
        return ;
    }
}
